package com.yangzhe.algorithm.c027;

import java.io.*;
import java.util.Arrays;

/**
 * 最多线段重合问题
 * 测试链接 : https://www.nowcoder.com/practice/1ae8d0b6bb4e4bcdbf64ec491f63fc37
 * 测试链接 : https://leetcode.cn/problems/meeting-rooms-ii/
 * 提交以下的code，提交时请把类名改成"Main"，可以直接通过
 *
 * 可以用差分、扫描线、线段树、树状数组，复杂度都是 复杂度 O(n * logn)，这里用堆的做法
 *
 * 每条线段都会进入堆一次 就是 n 次，每次进出都是 logn复杂度，所以最终复杂度就是 O(n * logn)
 */
public class Code02_MaxCover_Acm {
    private static int MAX_LENGTH = 10001;

    private static int[][] lines = new int[MAX_LENGTH][2];

    private static int n;

    public static void main(String[] args) throws IOException {
        try (
                InputStreamReader inputStreamReader  = new InputStreamReader(System.in);
                BufferedReader bufferedReader = new BufferedReader(inputStreamReader);
        ) {
            StreamTokenizer token = new StreamTokenizer(bufferedReader);
            token.nextToken();

            n = (int)token.nval;

            for (int i = 0; i < n; i++) {
                token.nextToken();
                lines[i][0] = (int)token.nval;
                token.nextToken();
                lines[i][1] = (int)token.nval;
            }
        }

        try (OutputStreamWriter streamWriter = new OutputStreamWriter(System.out);
             PrintWriter writer = new PrintWriter(streamWriter);
        ) {

            writer.print(maxCover());
            writer.flush();
        }
    }


    public static int maxCover() {
        heapSize = 0;
        Arrays.sort(lines, 0, n, (a, b) -> a[0] - b[0]);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            while (heapSize > 0 && lines[i][0] >= heap[0]) {
                pop();
            }
            heapInsert(lines[i][1]);

            if (heapSize > ans) {
                ans = heapSize;
            }
        }


        return ans;
    }

    /**
     * 小根堆
     */
    private static int[] heap = new int[MAX_LENGTH];

    private static int heapSize = 0;

    /**
     * 小根堆 小的向上调整 父节点index = (index - 1) / 2
     */
    private static void heapInsert(int value) {
        heap[heapSize] = value;
        int index = heapSize++;

        while(heap[(index -1) / 2] > heap[index]) {
            swap((index -1) / 2, index);
            index = (index -1) / 2;
        }
    }

    /**
     * 小根堆 大的向下调整
     * 子节点 左index = index * 2 + 1
     * 子节点 右index = index * 2 + 2
     */
    private static void heapify(int index) {
        while(index * 2 + 1 < heapSize) {
            // 1. 选出子节点中 左右两个节点中最小的节点的index
            int leftIndex = index * 2 + 1;
            int rightIndex = leftIndex + 1;
            int bestIndex = rightIndex < heapSize && heap[rightIndex] < heap[leftIndex] ? rightIndex : leftIndex;

            // 2. 如果当前节点比最小的节点还大，那么就需要向下调整
            if (heap[index] > heap[bestIndex]) {
                swap(index, bestIndex);
                index = bestIndex;
            } else {
                break;
            }
        }
    }

    /**
     * 弹出
     */
    private static int pop() {
        if (heapSize == 0) {
            return -1;
        }
        // 弹出最小节点
        int result = heap[0];

        // 把最后一个节点交换到0节点，之后heapify，则还是小根堆
        heap[0] = heap[--heapSize];
        heapify(0);

        return result;
    }

    private static void swap(int x, int y) {
        int temp = heap[x];
        heap[x] = heap[y];
        heap[y] = temp;
    }
}